This invention relates to methods and apparatus for breaking text into lines.
One operation commonly performed in preparing text materials for printing or displaying is to divide paragraphs into individual lines. When done well, readers hardly notice that the words have been arbitrarily broken into a plurality of lines. When done poorly, readers notice awkward line breaks that interrupt their train of thought, requiring more time and effort to read the text.
A conventional method for breaking a paragraph into lines determines appropriate line breaks by analyzing one line at a time. Words are added to a line until a suitable length is obtained, at which point a break is made and a new line is started. Although this method is relatively simple and fast, it fails to take into consideration that the final appearance of the paragraph as a whole and how the appearance of a given line is influenced by preceding and succeeding lines.
As discussed in Donald E. Knuth and Michael F. Plass""s article entitled xe2x80x9cBreaking Paragraph Into Lines,xe2x80x9d Software-Practice and Experience, Vol II, pp. 1119-1184 (1981), optimal line breaks may be selected by considering all feasible line breaks for one paragraph. The articles describes a method that evaluates all combinations of line breaks for a given paragraph and selects an optimal set of line breaks for the paragraph. This method was designed to operate in a batch-processing environment on a mainframe or minicomputer and not in an interactive environment of modem personal computers.
In general, in one aspect, the invention features methods and apparatus for dividing a paragraph into lines. The method includes the steps of selecting a first line break to define the end of a first line by evaluating possible line breaks for multiple possible lines in a first portion of the paragraph; and selecting a second line break to define the end of a second line following the first line by evaluating possible line breaks for multiple possible lines in a second portion of the paragraph, where the second portion overlaps the first portion but does not include words before the first line break.
Among the advantages of the invention are the following. The invention determines optimal line breaks in a paragraph by considering feasible line breaks for a portion of the paragraph covering multiple lines. The invention requires less memory space and processing time even for a long paragraph because only a portion of the paragraph at a time is analyzed to determine optimal line breaks. This is particularly important when processing a long paragraph since possible combinations of line breaks grow exponentially for a linear increase of feasible line breaks. The invention therefore is advantageous in a real-time editing environment with memory, processing resource and time constraints.
For a fuller understanding of the nature and further advantages of the invention, reference should be made to the detailed description taken in conjunction with the accompanying drawings.